package leetcode每日一题;

/**
 * 1. 问题描述
 *      编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
 *
 * 2. 算法分析
 *      1. 暴力法 设置一个访问数组
 *      2. 双hash记录那些行和列出现0元素
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 零矩阵 {
    public static void main(String[] args) {

    }

    // 访问数组 + 暴力
    public void setZeroes1(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean[][] vis = new boolean[row][col];
        for(int x = 0; x < row; x++) {
            for(int y = 0; y < col; y++) {
                if(vis[x][y] == false && matrix[x][y] == 0) {
                    vis[x][y] = true;
                    for(int i = 0; i < row; i++) {
                        if(matrix[i][y] != 0) {
                            matrix[i][y] = 0;
                            vis[i][y] = true;
                        }
                    }
                    for(int j = 0; j < col; j++) {
                        if(matrix[x][j] != 0) {
                            matrix[x][j] = 0;
                            vis[x][j] = true;
                        }
                    }
                }
            }
        }
    }


    // 双hash，记录出现0元素的行和列
    public void setZeroes2(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[] rows = new int[row];
        int[] cols = new int[col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0) {
                    rows[i] = 1;
                    cols[j] = 1;
                }
            }
        }

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(rows[i] == 1 || cols[j] == 1) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
